The Shortest Period [B]

Memory limit: 128 MB

A word is called a period of the word if it is not longer than and there exists a natural number such that is a prefix of . E.g., the periods of the word entente are: ent, entent and entente.

The teacher wrote a very long word on the whiteboard. Bytie was not really interested in what was the class about but he wrote down in his notebook all the words that can be obtained from the word on the whiteboard by removing exactly one letter. Now he would like to choose the word in his list with the shortest shortest period. Write a program that will help him with this problem.

Input

The first line of the standard input contains one integer (), the number of test cases. lines follow, each of them contains one integer () that denotes the length of the word on the whiteboard and a -letter word composed of small English letters.

Output

Your program should write lines to the standard output. The -th line should contain the answer for the -th test case: one integer equal to the length of the shortest period among all the shortest periods of the words written in Bytie's notebook.

Example

For the input data:

1
8 ababcaba

the correct result is:

2

Explanation of the example: Here are the words written by Bytie, together with the length of their shortest periods:

• babcaba - 5,
• aabcaba - 6,
• abbcaba - 6,
• abacaba - 4,
• abababa - 2,
• ababcba - 6,
• ababcaa - 6,
• ababcab - 5.

Task author: Jacek Tomasiewicz.